/**
 * @file bit.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-30
 * 
 * @copyright Copyright (c) 2021
 * 
 * 位运算相关
 * 15.二进制中1的个数
 * 16.数值的整数次方
 * 17.打印1到最大的n位数 -- 大数暂未考虑，留
 * 
 * 56.I.数组中数字出现的次数I
 * 56.II.数组中数字出现的次数II
 */

#include <cmath>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
public:
    // 15. 汉明重量
    int hammingWeight(uint32_t n)
    {
        // 位运算
        // 与运算 n & 1 = 1 最后一位是1
        // 结合移位和与运算
        int cnt = 0;
        while (n) {
            if (n & 1 == 1) {
                ++cnt;
            }
            n >>= 1;
        }
        return cnt;
    }
    // 16. 不使用库函数实现pow(x,n)
    double myPow(double x, int n)
    {
        if (n == 0) {
            return 1.;
        }
        if (n == -1) {
            return 1. / x;
        }
        if (n & 1) { // 奇数
            return myPow(x * x, n >> 1) * x;
        }
        return myPow(x * x, n >> 1);
    }
#if 0
    double myPow(double x, int n)
    {
        long long N = n; //int会溢出
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }

private:
    // 快速幂 将复杂度从O(N)降至O(logN)
    double fastPow(double x, int n)
    {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        // n为偶数时 x^n=(x^2)^(n/2)
        // n为奇数时，会多出一个x来
        return n % 2 == 0 ? half * half : half * half * x;
    }
#endif
    // 17.
    vector<int> printNumbers(int n)
    {
        int size = pow(10, n) - 1; // 已知size=10^n-1
        vector<int> res(size, 0);
        for (int i = 0; i < size; ++i) {
            res[i] = i + 1;
        }
        return res;
    }
    // 56.I.
    vector<int> singleNumbers(vector<int> &nums)
    {
        int x = 0, y = 0, n = 0, m = 1;
        for (int num : nums) // 1. 遍历异或
            n ^= num;
        while ((n & m) == 0) // 2. 循环左移，计算 m
            m <<= 1;
        for (int num : nums) { // 3. 遍历 nums 分组
            if (num & m)
                x ^= num; // 4. 当 num & m != 0
            else
                y ^= num; // 4. 当 num & m == 0
        }
        return vector<int>{x, y}; // 5. 返回出现一次的数字
    }
    // 56.II.
    int singleNumber(vector<int> &nums)
    {
        vector<int> counts(32, 0);
        for (int &num : nums) {
            for (int j = 0; j < 32; j++) {
                counts[j] += num & 1;
                num >>= 1;
            }
        }
        int res = 0, m = 3;
        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res |= counts[31 - i] % m;
        }
        return res;
    }
};